1. Field of the Invention
This invention relates to digital signal processing. Specifically, this invention relates to data buffering.
2. Description of Related Art and General Background
As shown in FIG. 1, a data path within a digital processing system or circuit may comprise several stages, wherein each stage may be characterized as a data producer and/or as a data consumer. In this example, stage 10 consumes data signals 40 and 80 and produces data signal 50, stage 20 consumes data signal 50 and produces data signals 60 and 90, and stage 30 consumes data signal 60 and produces data signal 70. Stage 15 is exclusively a data producer (for example, a read-only memory) and produces data signal 80, and stage 25 is exclusively a data consumer (for example, a display module) and consumes data signal 90.
Each such stage may be implemented in hardware and/or in software and may be defined, for example, as a portion or the entirety of a component, a circuit, a device, a process, a module, or a thread. The various stages in a data path may be a part of the same circuit or program, or they may be at opposite ends of a communications or storage application. Stages may also be defined at various levels of resolution, and a stage as defined at one level may comprise a collection of stages as defined at another level. The transmission of data between stages generally occurs along serial and/or parallel signal lines or channels.
A need often arises for the storage of data between two stages. For example, a differential may exist between the time that a data-producing stage (i.e. a producer) produces a quantity of data and the time that a data-consuming stage (i.e. a consumer) consumes that quantity of data. Data passing between such coupled stages are transitory, being defined only over some duration of time. If the data are not consumed before a new quantity of data is produced (or before control of the data signal line or channel is released), they may be lost.
Typically, the periphery of a data path is occupied by stages whose rates of data input or output are strictly defined by requirements of physical devices (e.g., devices for video or audio recording or presentation) or standards requirements (e.g., for modems or other communications controllers). Behind these peripheral stages are one or more processing stages which may be constrained to produce or consume data at different rates than those of the peripheral stages. In order to prevent a data loss resulting from the rate mismatch, it may be necessary to provide data storage between the peripheral and processing stages.
For example, data rate mismatches may arise within systems for digital communications. Certain stages of such an application may produce or consume data at a constant, uniform rate (e.g., sampling of an analog speech signal or the modulation or demodulation of a signal), while other stages may alternate between data processing and data input/output, thereby exhibiting data rates that are not constant over time (e.g., block-based processes such as error correction coding/decoding and block interleaving/deinterleaving). Although the average rates of production and consumption may be equal, the difference between the short-term characteristics of the rates may result in data loss if the two stages are connected directly. In order to reconcile the disparity between production and consumption when a constant-rate stage is data-coupled to a stage operating under a non-constant rate, some form of intermediate storage or buffering may be required.
One buffering scheme that may be used is the double buffer. In one implementation of a double buffer as shown in FIG. 2, data is alternately stored into one of two storage units 120 and 130 while previously stored data is retrieved from the other storage unit. The combination of demultiplexer 100, multiplexer 110, and inverter 140 operate under the direction of clock signal 150, directing input data signal 160 into one storage unit while producing output data signal 170 from data outputted by the other storage unit. In this manner, a constant input and/or output data rate may be maintained as desired. The size of the storage units 120 and 130 and the frequency of clock signal 150 are determined by factors such as the rates of the input and output data signals 160 and 170.
While double buffering techniques may be used to solve problems of data rate mismatches, however, cost and space considerations arise in connection with their implementation. Circuit elements for data storage are expensive in terms of area occupied. If a particular application requires a large amount of buffer capacity between two stages, then a significant amount of the available circuit area may be consumed by data storage. If the buffer area required by a proposed design can be reduced, on the other hand, it may be possible to reduce the total circuit size as well. Unfortunately, the minimum buffer capacity is typically dictated by other constraints such as processing block size and relative rates of data production and consumption.
A novel apparatus is disclosed which comprises (1) control logic and (2) data storage having three portions. The control logic causes a first part of a data block to be stored in the first portion of the data storage and the remainder of the data block to be stored in the second portion of the data storage.
Over some period of time, the control logic causes the remainder of the data block to be retrieved from the data storage. During the same period, the control logic causes a second data block to be stored into the data storage, such that the first part of the second data block is stored in the first portion of the data storage and the remainder of the second data block is stored in the third portion of the data storage.